public class MyLinkedList implements IList{

    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
    public ListNode last;

    @Override
    public void addFirst(int data) {
        ListNode cur=head;
        ListNode node =new ListNode(data);
        if (cur==null) {
            head=last=node;
            return;
        }
        node.next=head;
        head.prev=node;
        head=node;
    }

    @Override
    public void addLast(int data) {
        ListNode cur=head;
        ListNode node =new ListNode(data);
        if (cur==null){
            head=last=node;
            return ;
        }
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
        node.prev=cur;
        last=node;
    }

    @Override
    public void addIndex(int index, int data) {
        if (head==null)
            return;
        ListNode node =new ListNode(data);
        ListNode cur=head;
        int len =size();

        if (index<0||index>len)
            return;
        if (index==0){
            addFirst(data);
            return;
        }
        if (index==len){
            addLast(data);
            return;
        }
        while(index!=0){
            cur=cur.next;
            index--;
        }
        node.prev=cur.prev;
        cur.prev.next=node;
        cur.prev=node;
        node.next=cur;

    }



    @Override
    public void remove(int key) {
        if (head==null) return;
        ListNode cur=head.next;

        if (head.val==key){
            if(head.next!=null){
                head.next.prev=null;
            }
            head=head.next;
            return;
        }

        while(cur.next!=null){
            if(cur.val==key){
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
                return;
            }
            cur=cur.next;
        }

        if(last.val==key){
            if (last.prev!=null){
                last.prev.next=null;
            }
            last=last.prev;
            return;
        }
    }

    @Override
    public void removeAllKey(int key) {
        if (head==null) return;
        ListNode cur=head.next;

        if (head.val==key){
            if(head.next!=null){
                head.next.prev=null;
            }
            head=head.next;
        }

        while(cur.next!=null){
            if(cur.val==key){
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
            }
            cur=cur.next;
        }

        if(last.val==key){
            if (last.prev!=null){
                last.prev.next=null;
            }
            last=last.prev;
        }
    }



    @Override
    public void clear() {
        ListNode cur=head;
       while(cur!=null){
           ListNode node =cur.next;
           cur.next=null;
           cur=node;
       }
       last.prev=null;
    }

    @Override
    public void display() {
        ListNode cur=head;
        if (cur==null)
            return;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }


    public void display(ListNode head1) {
        ListNode cur=head1;
        if (cur==null)
            return;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    @Override
    public int size() {
        if (head==null)
        return 0;
        ListNode cur=head;
        int len=0;
        while(cur!=null){
            len++;
            cur=cur.next;
        }
        return len;
    }

    @Override
    public boolean contains(int key) {
        if (head==null)
        return false;
        ListNode cur=head;
        while(cur!=null){
            if (cur.val==key){
                return true;
            }
        }
        return false;
    }
    public ListNode partition(int x) {
        if(head==null) return null;
        ListNode headA=new ListNode(1);
        ListNode cur1=headA;
        ListNode headB=new ListNode(2);
        ListNode cur2=headB;

        while(head!=null){
            if(head.val<x){
                cur1.next=head;
                cur1=cur1.next;
                head=head.next;
                cur1.next=null;
            }else{
                cur2.next=head;
                cur2=cur2.next;
                head=head.next;
                cur2.next=null;
            }
        }
        cur1.next=headB.next;
        return headA.next;
    }
}
